package ch1;

import static javafx.scene.input.KeyCode.L;

/**
 * 检查一个字符串中是否有相同字符
 * @author tantexian
 * @since 2016/10/22
 * @params
 */
public class ch1_1 {
    public static void main(String args[]) {
        String str = "abcd1234";
        System.out.println(isSameCharInString(str));

        str = "abcdABCDJKLzZ";
        System.out.println(isSameCharInString1(str));
    }


    // 该算法的时间复杂度为O(n),空间复杂度为O(1)
    // 此算法基于所有ASCII字符个数为256个
    static boolean isSameCharInString(String str) {
        // 总共字符只有256个，如果大于256个，则肯定有重复的
        if (str.length() > 256) {
            return true;
        }

        boolean[] charAt = new boolean[256];

        for (int i=0; i< str.length(); i++) {
            int val = str.charAt(i);

            // 該字符串之前已經出现过
            if (charAt[val] == true) {
                return true;
            } else {
                charAt[val] = true;
            }
        }

        return false;
    }

    // 此算法基于所有ASCII字符个数只有A-z为52个。则可以使用一个long(8个字节，64bit)来保存所有boolean值
    static boolean isSameCharInString1(String str) {
        if (str.length() > 52) {
            return true;
        }

        long charAtLong = 0l;
        for(int i = 0; i < str.length(); i++) {
            // 由于ASCII的A字符为65，因此将ASCII的值依次减少65
            int val = str.charAt(i) - 'A';

            // 检测当前字母是否已经在之前出现过了
            long tmpLong = charAtLong;
            // 向右位移val位，将高位置零，即可得到charAtLong的第val位的值
            tmpLong = (tmpLong >> val) & 1;
            if (tmpLong == 1) {
                return true;
            }else { // 讲charAtLong的第val位设置为1
                charAtLong = charAtLong | (1 << val);
            }
        }

        System.out.println(Long.toBinaryString(charAtLong));
        return false;
    }
}
